import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	int[] values;

	public Main() throws IOException {
//		System.out
//				.println("Please input your integer values seperated by spaces.");
//		String[] temp = in.readLine().split(" ");
//		// Convert into an array of integers.
//		values = new int[temp.length];
//		for (int i = 0; i < temp.length; i++) {
//			values[i] = Integer.parseInt(temp[i]);
//		}
		values = new int[10];
		for (int i = 0; i < values.length; i++){
			values[i] = (int)(Math.random()*9999999);
		}
		long time = System.currentTimeMillis();
		System.out
				.println("What sorting method would you like to use? (1)Bubble (2)Selection (3)Insertion");
		int input = Integer.parseInt(in.readLine());
		if (input == 1) {
			bubbleSort(values);
		} else if (input == 2) {
			selectSort(values);
		} else if (input == 3) {
			insertSort(values);
		}
		System.out.println(System.currentTimeMillis() - time);
		/*for (int i = 0; i < values.length; i++) {
			System.out.println(values[i] + " ");
		}*/
	}

	/**
	 * Goes through the entire array, storing the current value in a temporary
	 * integer. Starting from the current point, the array goes backwards to
	 * check if any of the previous values are greater than the current value.
	 * If so, the bigger value gets shifted ahead. Once the previous value is
	 * not larger, the loop breaks and the current array (in second loop) gets
	 * set to the temporary integer. Alternatively another variable can be used
	 * to set up to which position has already been sorted, but the break does
	 * the job.
	 */
	private void insertSort(int[] values) {
		int temp;
		for (int i = 1; i < values.length; i++) {
			temp = values[i];
			for (int x = i; x > 0; x--) {
				if (values[x - 1] > temp) {
					values[x] = values[x - 1];
				} else {
					values[x] = temp;
					break; // By using a break, there is no need to remember how
							// much has already been sorted.
				}
			}
		}
	}

	/**
	 * Goes through the entire array, setting the current value as the minimum.
	 * After that it goes through the array again starting from the value after
	 * the current and remembers the lowest value and its index. This lowest
	 * value gets swapped with the current value in the outer loop.
	 */
	private void selectSort(int[] values) {
		for (int i = 0; i < values.length; i++) {
			int min = values[i], index = i;
			for (int x = i + 1; x < values.length; x++) {
				if (values[x] < min) {
					min = values[x];
					index = x;
				}
			}
			values[index] = values[i];
			values[i] = min;
		}
	}

	/**
	 * Continues while the flag is set to true. The flag gets set to true if a
	 * value has been swapped. Goes through the entire array slowly shifting the
	 * larger values to the end. If the current value is bigger than the next
	 * value, it shifts it over using a temporary holder.
	 */
	private void bubbleSort(int[] values) {
		int temp;
		boolean flag = true;
		while (flag) {
			flag = false;
			for (int i = 0; i < values.length - 1; i++) {
				if (values[i] > values[i + 1]) {
					temp = values[i];
					values[i] = values[i + 1];
					values[i + 1] = temp;
					flag = true;
				}
			}
		}

	}

	public static void main(String[] args) throws IOException {
		new Main();
	}
}
